#define _CRT_SECURE_NO_WARNINGS
#include "Binary.h"

int BinaryTreeSize(BTNode* root) {
	if (root==NULL) {
		return 0;
	}
	
	if (root->_left == NULL && root->_right == NULL) {
		return 1;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right)+1;
	
}
int TreeHeight(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	int left = TreeHeight(root->_left);
	int right = TreeHeight(root->_right);
	if (left > right) {
		return left + 1;
	}
	return right + 1;
}
void BinaryTreePrevOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
void BinaryTreeInOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}
void BinaryTreePostOrder(BTNode* root) {
	if (root == NULL) {
		return;
	}

	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c \n", root->_data);
}
BTNode* BinaryTreeCreate(BTDataType* a, int* pi) {
	assert(a);
	if (a[*pi] == '#') {
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	root->_data = a[(*pi)++];
	root->_left = BinaryTreeCreate(a, pi);
	root->_right = BinaryTreeCreate(a, pi);

	return root;
}
//void BinaryTreeDestory(BTNode** root) {
//	Queue q;
//	QueueInit(&q);
//	if (*root) {
//		QueuePush(&q, *root);
//	}
//	while (!QueueEmpty(&q)) {
//		BTNode* front = QueueFront(&q);
//		QueuePop(&q);
//		if (front->_left) {
//			QueuePush(&q, front->_left);
//		}
//		if (front->_right) {
//			QueuePush(&q, front->_right);
//		}
//		free(front);
//	}
//	QueueDestroy(&q);
//	*root = NULL;
//}


void BinaryTreeDestory(BTNode** root) {
	if (*root == NULL)
		return;
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	free(*root);
}

int BinaryTreeLeafSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->_left == NULL && root->_right == NULL) {
		return 1;
	}
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);

}
int BinaryTreeLevelKSize(BTNode* root, int k) {
	if (root == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;
	BTNode* left = BinaryTreeFind(root->_left,x);
	if (left) {
		return left;
	}
	BTNode* right = BinaryTreeFind(root->_right,x);
	
	if(right) {
		return right;
	}
	return NULL;
}
void BinaryTreeLevelOrder(BTNode* root) {
	Queue q;
	QueueInit(&q);
	if (root) {
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		printf("%c ", front->_data);
		QueuePop(&q);
		if (front->_left) {
			QueuePush(&q, front->_left);
		}
		if (front->_right) {
			QueuePush(&q, front->_right);
		}
	}
	QueueDestroy(&q);
	printf("\n");
}
bool BinaryTreeComplete(BTNode* root) {
	Queue q;
	QueueInit(&q);
	if (root) {
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front==NULL) {
			break;
		}
		else {
			QueuePush(&q, front->_left);
			QueuePush(&q, front->_right);
		}
	}
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		if (front != NULL) {
			QueueDestroy(&q);
			return false;

		}
		QueuePop(&q);
		
	}
	QueueDestroy(&q);
	return true;
}